export class Dijkstra {
    // 顶点列表
    private vertexList: string[] = [];
    // 各顶点距离 (无向图)
    private vertexMap: Map<string, number> = new Map();
    private flagVertex: { [vertexId: string]: boolean } = {};

    private preVertex: { [vertexId: string]: string } = {};

    private MAX_LEN = 20000; // 默认最大距离,实际值不会大于该值
    constructor(vList: string[], map: Map<string, number>) {
        this.vertexList = vList;
        this.vertexMap = map;
    }

    twoVertexLen(oneVertex: string, otherVertex: string) {
        let vLen = this.vertexMap.get(oneVertex + "-" + otherVertex);
        vLen = vLen ? vLen : this.vertexMap.get(otherVertex + "-" + oneVertex);
        return vLen ? vLen : this.MAX_LEN;
    }

    findPath(v: string): { [vertexId: string]: string } {
        const vertexNum = this.vertexList.length;
        // 标级已遍历过的顶点
        this.flagVertex[0] = true;

        for (let index = 0; index < vertexNum; index++) {
            let minLen = this.MAX_LEN;
            let minVertexId: string | undefined;
            for (let i = 0; i < vertexNum; i++) {
                const vertexId = this.vertexList[i];
                if (!this.flagVertex[vertexId]) {
                    const twoVerLen = this.twoVertexLen(v, vertexId);
                    if (twoVerLen < minLen) {
                        minVertexId = vertexId;
                        minLen = twoVerLen;
                    }
                }
            }

            if (minVertexId) {
                // 更新邻近节点到起点的距离
                this.flagVertex[minVertexId] = true;
                for (let i = 0; i < vertexNum; i++) {
                    const vertexId = this.vertexList[i];
                    if (!this.flagVertex[vertexId]) {
                        const twoVerLen = this.twoVertexLen(minVertexId, vertexId);
                        const startVerLen = this.twoVertexLen(v, vertexId);
                        if (twoVerLen + minLen < startVerLen) {
                            this.vertexMap.set(v + "-" + vertexId, twoVerLen + minLen);
                            this.preVertex[vertexId] = minVertexId;
                        }
                    }
                }
            }
        }

        return this.preVertex;
    }
}
